package com.zlp.partice;

import org.junit.Test;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: zhulaiping
 * @Date: 2021/11/3 14:43
 */
public class interview {

    static ThreadLocal<String> local = new ThreadLocal<>();


    @Test
    public void ee(){
        byte a = 127;
        byte b = 127;
        //b += a;
        System.out.println(b);
        isPerfectSquare(808201);


    }
    public boolean isPerfectSquare(int num) {
        if(num==1 || num == 4) return true;
        int l = 1,r = num/2;
        while (l<=r){
            long mid = l + (r-l>>1);
            if(mid*mid == num) {
                return true;
            } else if(mid*mid < num){
                l = (int) mid+1;
            } else{
                r = (int) mid-1;
            }
        }
        return false;
    }
    int[] dp = new int[201];
    public void Solution(){
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 3;
        for (int i=5;i<201;i++){
            dp[i] = i-3+Math.max(dp[i-4],i-1);
        }
    }
    int[][] cache = new int[201][201];
    public int getMoneyAmount(int n) {
        return def(1,n);
    }
    private int def(int start, int n) {
        if(cache[start][n] != 0) return cache[start][n];
        if(start == n) return 0;
        if(start+1 == n) return cache[start][n] = start;
        int ret = Integer.MAX_VALUE;
        //最小代价使得我们取整体最小值
        //确保猜对，导致了我们每个值都需要猜，则需要取全局最大值
        for (int i=(start+n)/2;i<n;i++){
            ret = Math.min(ret,i+Math.max(def(i+1,n),def(start,i-1)));
        }
        return cache[start][n] = ret;
    }


    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int temp = grid[row][col];
        int[][] visited = new int[grid.length][grid[0].length];
        return null;
    }




    @Test
    public void eq(){
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }

    public List<Integer> findAnagrams(String s, String p) {
        int[] sarr = new int[26],parr = new int[26];
        for(int i=0;i<p.length();i++){
            if(i<p.length()-1) sarr[s.charAt(i)-'a']++;
            parr[p.charAt(i)-'a']++;
        }
        List<Integer> ret = new ArrayList<>();
        for(int i=p.length()-1;i<s.length();i++){
            sarr[s.charAt(i)-'a']++;
            if(compare(sarr,parr)){
                ret.add(i-p.length()+1);
            }
            sarr[s.charAt(i-p.length()+1)-'a']--;
        }
        return ret;
    }
    private boolean compare(int[] s,int[] p){
        for(int i=0;i<26;i++){
            if(s[i]!=p[i]){
                return false;
            }
        }
        return true;
    }

}
